package com.cjm.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/maximum-average-subarray-i/">子数组最大平均数</a>
 * <p>
 * 给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
 * <p>
 * 请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
 * <p>
 * 任何误差小于 10-5 的答案都将被视为正确答案。
 */
public class FindMaxAverage643 {
    public double findMaxAverage1(int[] nums, int k) {
        // nums数组, 整数k
        // 平均数最大, 长度=k
        double sum = 0;
        int total = 0;
        double mu = k * 1.00000;
        double rev = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            total++;
            sum += nums[i];
            if (total >= k) {
                sum = (i - k) >= 0 ?sum - nums[i - k] : sum;
                double crev = sum / mu;
                rev = Math.max(rev, crev);
            }
        }
        return rev;
    }

    public double findMaxAverage(int[] nums, int k) {
        // nums数组, 整数k
        // 平均数最大, 长度=k
        double max = 0.00000;
        int pre = Integer.MAX_VALUE;
        double x = k * 1.00000;
        for (int l = 0, r = k - 1; r < nums.length; l++, r++) {
            if (pre == Integer.MAX_VALUE) {
                int cur = 1;
                int sum = 0;
                while (cur <= r) {
                    sum += nums[cur++];
                }
                pre = sum;
                max = (pre / x);
            } else {
                pre = pre - nums[l - 1] + nums[r];
                max = Math.max(max, (pre / x));
            }
        }
        return max;
    }

    public static void main(String[] args) {
        FindMaxAverage643 findMaxAverage643 = new FindMaxAverage643();
//        int[] x = new int[]{-6662, 5432, -8558, -8935, 8731, -3083, 4115, 9931, -4006, -3284, -3024, 1714, -2825, -2374, -2750, -959, 6516, 9356, 8040, -2169, -9490, -3068, 6299, 7823, -9767, 5751, -7897, 6680, -1293, -3486, -6785, 6337, -9158, -4183, 6240, -2846, -2588, -5458, -9576, -1501, -908, -5477, 7596, -8863, -4088, 7922, 8231, -4928, 7636, -3994, -243, -1327, 8425, -3468, -4218, -364, 4257, 5690, 1035, 6217, 8880, 4127, -6299, -1831, 2854, -4498, -6983, -677, 2216, -1938, 3348, 4099, 3591, 9076, 942, 4571, -4200, 7271, -6920, -1886, 662, 7844, 3658, -6562, -2106, -296, -3280, 8909, -8352, -9413, 3513, 1352, -8825};
        int[] x = new int[]{1,12,-5,-6,50,3};
        System.err.println(x.length);
        System.err.println(findMaxAverage643.findMaxAverage1(x, 4));
    }
}
